/*最小度限制生成树即为对度有限制的最小生成树，Lrj书上经典的例子。这里度限制是指只对一个顶点的度数有限制，而如果是所有的点都有限制的话,那就是NP问题了。


具体步骤：（算法的证明可以参照lrj的《算法艺术和信息学竞赛》）

（我们假定度有限制的结点为V0）

1. 求出除去V0，其他每个森林的最小生成树（除去V0后，其他的点不一定都是连通的）。
       2. 在每个森林中找出与V0距离最近的点，并与V0相连（此时即为一棵生成树，这棵生成树的根结点为V0，即在与V0相连时，要修改前驱数组pre[]）。

3. 循环 （度数 – 森林数）次，每次找到g[0][i] – max_value[i]最小的i结点，其中max_value[i]为Vi到V0的路径上不与V0相连的边的最大权值。

如果g[0][i] – max_value[i] >= 0说明已经是最优解了，退出。

否则加入g[0][i]这条边，删去Vi到V0的路径上不与V0相连的最大权值的边。


这里算法的瓶颈在于如何快速快速找到“Vi到V0的路径上不与V0相连的边的最大权值”。一开始我是用O(kn2)的模拟，即每次从Vi向上找到根结点，求出最大权值。提交上去16ms。

Lrj书上说可以用max_value[i]记录Vi到V0的路径上不与V0相连的边的最大权值，而初始化和维护都只要O(n)，想了半天，发现其实就是递推呀。我们可以从Vi向上找到根结点，再用栈反向递推回来，即：

max_value[Stack[i]] = MAX(max_value[Stack[i + 1]], g[Stack[i]][ pre[Stack[i]]]

还可以用数组max_value_v记录最大权值的边的起点。这样每次只要直接比较g[0][i] – max_value[i]，找到最小值，然后添加(i, 0)边，并修改Vi到V[max_value_v[i]]的前驱数组pre[]，再，反向递推求出V[max_value_v[i]]到 V0路径上结点的max_value值。

这样第3步的复杂度就降为O(kn)。
*/
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
using namespace std;
const int maxn=50;
const int inf = 1012345678;
/*********度限制生成树模板*****************/
//最小K度限制生成树
const int maxcost=(1<<28);
int g[maxn][maxn];//邻接矩阵,从1开始到N，表示图中任意两点距离
int all,has,ans,source;//all总共的点数包括度限制点从1到all,度限制是has，最小has度限制生成树的答案，度限制点source
int pre[maxn],father[maxn],best[maxn],dist[maxn];
bool vis[maxn],mark[maxn],edge[maxn][maxn];
void dfs(int root)//将一棵最小生成树中各个点标记其father
{
 int i;
 for(i=1;i<=all;i++)
  if(!mark[i]&&!edge[root][i])
  {
   father[i]=root;
   mark[i]=true;
   dfs(i);
  }
}
void prim(int s)//求最小生成树
{
 int i,j,min,k;
 memset(mark,true,sizeof(mark));
 for(i=1;i<=all;i++)
 {
  pre[i]=s;
  dist[i]=g[s][i];
 }
 mark[s]=false;vis[s]=false;
 while(1)
 {
  min=maxcost;k=-1;
  for(i=1;i<=all;i++)
   if(vis[i]&&mark[i]&&dist[i]<min)
   {
    min=dist[i];k=i;
   }
   if(k==-1) break;
   mark[k]=false;vis[k]=false;
   edge[pre[k]][k]=edge[k][pre[k]]=false;
   ans+=min;
   for(i=1;i<=all;i++)
    if(vis[i]&&mark[i]&&g[k][i]<dist[i])
    {  dist[i]=g[k][i]; pre[i]=k;}
 }
    min=maxcost;
 int root=-1;
 for(i=1;i<=all;i++)
  if(!mark[i]&&g[source][i]<min&&i!=source)
  {  min=g[source][i]; root=i;}
  mark[root]=true;
  dfs(root);
  father[root]=source;
  ans+=min;
}
int Best(int j)//更新其中各个点到source路径上边权值最大的点
{
 if(father[j]==source)//如果father为source，记为-1
  return best[j]=-1;
 if(best[j]!=-1) return best[j];//如果已经存在 ，直接返回
 int tmp=Best(father[j]);
 if(tmp!=-1)//这说明其父节点不与source相连
 {
  if(g[tmp][father[tmp]]>g[father[j]][j])
   best[j]=tmp;
  else best[j]=j;
 }
 else best[j]=j;//其父节点与source相连  将j赋给自己
 return best[j];
}
void solve()
{
	 int i,j;
	 int mst=0;
	 memset(father,-1,sizeof(father));
	 memset(vis,true,sizeof(vis));
	 memset(edge,true,sizeof(edge));
	 vis[source]=false;
	 for(i=1;i<=all;i++)//求得各个连通分量里的最小生成树
	 {
	  if(vis[i])
	  {
	   mst++;
	   prim(i);
	  }
	 }
    for(i=mst+1;i<=all&&i<=has;i++)//求m+1度限制  直到为K
    {
        memset(best,-1,sizeof(best));
        for(j=1;j<=all;j++)
            if(j!=source&&best[j]==-1&&father[j]!=source)
                Best(j);
        int minadd=maxcost;
        int ax,bx,change;
        for(j=1;j<=all;j++)
            if(g[source][j]!=maxcost&&father[j]!=source)
            {
                ax=best[j];
                bx=father[ax];
                if(minadd>g[source][j]-g[ax][bx])
                {
                     minadd=g[source][j]-g[ax][bx];
                     change=j;
                }
            }
            if(minadd>=0) break;
            ans+=minadd;
            ax=best[change];
            bx=father[ax];
            g[ax][bx]=g[bx][ax]=maxcost;
            father[change]=source;
            g[source][change]=g[change][source]=maxcost;
    }
}

/*********度限制生成树模板*****************/
map<string,int> mp;
int m;
void input()
{
    mp.clear();
    for(int i=1;i<maxn;i++)
     for(int j=1;j<maxn;j++) 
    	g[i][j]=inf;
    char s[25],t[25];
    int u,v,w;
    int cnt=0;//从1开始 ++cnt
    for(int i=0;i<m;i++)
    {
        scanf("%s%s%d",s,t,&w);
        if(mp[s]==0) mp[s]=++cnt;
        if(mp[t]==0) mp[t]=++cnt;
        u=mp[s],v=mp[t];
        /*********度限制生成树模板*****************/
        if(g[u][v]>w) g[u][v]=g[v][u]=w;//无向图
    	/*********度限制生成树模板*****************/
    }
    /*********度限制生成树模板*****************/
    all=cnt;//点数,总共的点数
    scanf("%d",&has);//度限制
	/*********度限制生成树模板*****************/
}
int main()
{
    while(scanf("%d",&m)==1)
    {
        input();
        source=mp["Park"];//度限制点
        ans=0;
        solve();
        printf("Total miles driven: %d\n",ans);
    }
 return 0;
}
